package hot;



/**
 * @author lakersUp
 * @Classname       分割等和子集
 * @Description
 * @Date 2022/4/1 11:19
 * @Version 1.0
 */
public class Hot416canPartition {
    public boolean canPartition(int[] nums){
        if(nums.length==1){
            return false;
        }
        int sum=0;
        for (int num : nums) {
            sum+=num;
        }
        if(sum%2!=0){
            return false;
        }
        sum/=2;
        boolean[][] dp = new boolean[nums.length][sum+1];
        //初始化
        for(int i=0;i<nums.length;i++){
            dp[i][0]=true;
        }
        dp[0][nums[0]]=true;

        for(int i=1;i<nums.length;i++){
            for(int j=1;j<=sum;j++){
                if(j>=nums[i]){
                    dp[i][j]=dp[i-1][j] | dp[i-1][j-nums[i]];
                }
                else {
                    dp[i][j]=dp[i-1][j];
                }
            }
        }
        return dp[nums.length-1][sum];

    }
}
